1. Field of the Invention
This invention relates to a system and method for scheduling a complex activity that includes performance of a multiplicity of tasks, the completion of which necessitates the use of a multiplicity of resources and adherence to state requirements of a multiplicity of attributes. The tasks, resources and attributes are related by a multiplicity of constraints. At least some of the resources are consumable resources. In particular, the invention relates to such a system and method that combine the techniques of constraint-based iterative repair with the techniques of material requirements planning.
2. Related Art
Management of a complex activity, such as operation of a manufacturing facility, or maintenance and repair of a complex system such as the Space Shuttle, necessitates scheduling of many tasks, the completion of which may conflict with each other for a variety of reasons. Further, each of the tasks uses resources (which can be either consumable or reusable) of finite extent. Development of a schedule that resolves the many possible conflicts that may arise during conduct of the activity is a complex problem. The problem is further compounded by the probability that unforeseen events will, from time to time, necessitate modification of any determined schedule.
"Scheduling" is the process of assigning times and resources to the tasks of an operation. Scheduling assignments must satisfy a set of constraints. Constraints include, for example, temporal constraints, milestone constraints, resource constraints, state constraints and preemptive constraints.
Constructive scheduling is one method that has been used to develop schedules for complex activities. In constructive scheduling, a partial schedule is developed from scratch so that the partial schedule does not violate any of the constraints (or violates the constraints to a predefined acceptable degree). The partial schedule is then incrementally extended through a series of successive partial schedules, each successive partial schedule conforming to the constraints (again, to a predefined degree), until a final, complete schedule is developed. In some constructive scheduling methods, failure of any of the partial schedules to adequately satisfy the constraints necessitates backtracking to an earlier partial schedule and reconstructing a series of partial schedules from that point. Construction of partial schedules and backtracking continue until an acceptable final schedule is developed. In other constructive scheduling methods, when a partial schedule fails to satisfy a constraint, the schedule meets the constraint as best it can, and the constraint is relaxed to the degree necessary to eliminate the constraint violation.
Constraint-based iterative repair is another method that has been used to develop schedules for complex activities. In constraint-based iterative repair, a complete schedule that does not adequately satisfy the constraints is iteratively modified to obtain a series of complete schedules until one of the modified schedules adequately satisfies the constraints. Unlike constructive methods, only constraints that have been violated are repaired during each iteration.
The above-described techniques have been used to solve "scheduling problems." A "scheduling problem" is a problem in which all of the items, e.g., tasks and resources, to be scheduled to accomplish an operation are known at the beginning of development of the schedule. Establishment of a schedule consists of assigning a time and allocating resources to each task such that the constraints are satisfied to the degree desired. An example of a scheduling problem is the assignment of classrooms, teachers and students for all of the courses offered at a university during a semester.
In contrast to a scheduling problem, with its pre-established set of tasks and resources, a "planning problem" is more open-ended. In a planning problem, any of a number of sets of tasks and resources can be chosen to accomplish an operation, subject only to the satisfaction of certain conditions during the scheduled set of activities. Thus, typically, while scheduling for a planning problem will begin with a defined set of tasks and resources, additional tasks and resources are added to the schedule as the final schedule is developed. (It is also possible to delete some tasks and resources during development of the final schedule.) Therefore, scheduling for "planning problems" is generally more complex than scheduling for "scheduling problems." Scheduling a manufacturing operation is a good example of a planning problem.
There are two primary types of planning problems: i) consumable resource planning, e.g., inventory planning such as planning for finished goods, raw material, and/or work-in-progress in a manufacturing operation, and ii) reusable resource planning, e.g., capacity planning such as planning for machine and labor usage in a manufacturing operation. Previously, these two planning problems have been addressed separately. Below, previous methods of addressing these problems are discussed in the manufacturing context.
In manufacturing, master production scheduling (MPS) has been used to address the inventory planning problem. MPS operates at a macrocosmic level and is used to develop a build schedule for the supply of finished goods, e.g., goods sold directly to a consumer. MPS accepts demand requirements as input, i.e., the quantity of finished goods needed at particular times. The demand requirements are forecasted and/or actual needs netted against existing inventory. MPS develops a schedule for the replenishment of the finished goods inventory by scheduling the production and/or procurement of batches of finished goods to meet the demand requirements. For example, MPS could be used to develop a build schedule for a particular model of computer made by a manufacturer.
Rough cut capacity planning has been used in the manufacturing context to address the capacity planning problem at the macrocosmic level. Typically, rough cut capacity planning evaluates capacity constraints at some level between the factory and machine levels, e.g., at the production line level. A build schedule, as developed by a MPS system for example, is input into the rough cut capacity planning system and a determination is made as to whether sufficient resources exist to implement the build schedule. If not, a planner must either direct that additional capacity be added, or develop a new build schedule using MPS techniques. For example, rough cut capacity planning can determine whether there are an adequate number of assembly lines and workers to produce a sufficient number of computers according to a build schedule established by an MPS system.
Typically, MPS and rough cut capacity scheduling are successively performed at least several times before a satisfactory build schedule is developed, one that accommodates both demand (inventory) requirements and capacity constraints. Inventory planning and capacity planning are not coupled, other than to supply the inventory planning (i.e., MPS) output as the capacity planning (i.e., rough cut capacity planning) input, and to use the capacity planning output to evaluate the efficacy of the inventory planning output. Solution of the combined inventory and capacity problem in this manner frequently takes a rather long time and does not lend itself to easy rescheduling once an acceptable build schedule has been established.
Once MPS and rough cut capacity planning have been used to develop a satisfactory build schedule for the supply of finished goods, the production requirements of the build schedule are supplied to a material requirements planning (MRP) system. MRP operates at a microcosmic level and is used to develop a schedule for the production of finished goods. As input, the MRP system accepts the production requirements of the build schedule, subassembly and raw materials inventory levels (to net production requirements against existing inventory), bills of materials (BOMs) associated with the production of the finished goods and subassemblies, and information regarding production and material ordering lead times. The MRP system outputs schedules for the ordering of raw materials and component parts, assembly of raw materials and component parts into sub-assemblies, and assembly of sub-assemblies into finished goods. MRP could be used, for example, to schedule the assembly of circuit boards and disk drives from raw materials and/or component parts, as well as the subsequent assembly of the circuit boards and disk drives (and other necessary components) to produce computers.
The schedule developed by an MRP system assumes infinite capacity. Since, in the real world, this is not so, the schedule developed by the MRP system can be input to a capacity resources planning (CRP) system to evaluate whether sufficient capacity resources are available at the times necessary to fulfill the MRP schedule. If not, then either additional capacity must be added, or the MRP system must produce a new schedule. However, like MPS and rough cut capacity planning, MRP and CRP are not coupled processes, so that development of a new schedule by the MRP system does not occur automatically, but rather must be initiated by a planner who makes changes to the demand requirements placed on the MRP system using knowledge not available to the planning systems, such as the ability of one part to be substituted for another.
Another approach used with MRP to solve the capacity problem is finite capacity scheduling (FCS). FCS systems may have a limited ability to perform some automatic rescheduling. However, they do not extensively couple capacity constraints to inventory requirements and so do not adequately optimize a schedule based upon consideration of capacity constraints. Several types of FCS have been tried, each type enabling consideration of only a small subset of schedules out of the entire realm of possible schedules that can satisfy the inventory and capacity constraints.
One type of FCS uses mathematical programming techniques, such as linear programming or integer programming (e.g., a branch and bound method), to develop an acceptable schedule. Mathematical programming techniques can ensure that the best possible schedule is found. However, evaluation of alternative schedules requires reformulation of the schedule from scratch, i.e., these techniques are constructive methods, making this approach very slow in producing the final schedule. Further, mathematical programming necessitates complex mathematical formulations and a large number of variables to define the scheduling problem, thus necessitating a large information storage capacity and a lengthy time for execution of the scheduling procedure. Thus, mathematical programming is not suitable for use in situations where frequent and rapid rescheduling is required, as is frequently the case. Additionally, linear programming requires a linear optimization function and real-valued variables, conditions that are too restrictive for many scheduling problems.
Another type of FCS, "dispatching and simulation," uses a set of rules to produce a schedule that satisfies both inventory and capacity constraints. Dispatching and simulation systems can include only very simple rules, or they can be implemented as rule-based expert systems and implement a more complex set of rules. However, this approach can only be used to produce a single solution--the method does not iterate through a series of solutions--so that the best schedule is usually not found. Further, once a scheduling problem has been defined, it is an arduous task to modify the problem definition to accommodate additions, revisions and deletions to the problem constraints, making dispatching and simulation a relatively inflexible approach to scheduling.
There are a number of other FCS methods, including case-based reasoning, genetic algorithms, and neural nets. All of these methods use some variation of iterative repair. Case-based reasoning is a method that matches a scheduling problem to a library of previously solved scheduling problems. When an analogous problem is found, the solution to that problem is repaired so as to make the solution applicable to the new problem. Since, in order to be useful, case-based reasoning methods require the acquisition of a voluminous amount of cases to be useful, they are overly time consuming. Even after training, case-based methods are typically slow because of the matching process.
Genetic algorithms and neural network algorithms are iterative repair methods that generally rely on very weak repairs such as random modifications or repairs that are analogous to biological gene mutations and crossovers. Because these algorithms have weak repairs, they typically require many iterations to converge to an acceptable schedule and, therefore, are slow. Further, since these methods rely on random repairs, they also tend to significantly alter schedules, making them undesirable for rescheduling applications. Standard applications of simulated annealing and tabu search also rely on random repairs rather than the exploitation of constraint knowledge, so they also suffer from the same problems--slowness and large schedule perturbation--as genetic and neural network algorithms.
None of the above-described approaches considers both inventory and capacity constraints simultaneously to a significant degree, and most do not consider the two together at all. As a result, those methods typically do not produce a schedule that is optimal with respect to both capacity and inventory constraints.
Further, those methods that do consider inventory and capacity together to a limited degree (FCS methods), suffer from other deficiencies. Integer programming requires complex modeling and is slow. Dispatching and simulation, and rule-based expert systems do not iterate through a series of solutions in order to obtain increasingly better solutions and are difficult to modify to change constraint definitions.
Additionally, all of the above-described methods produce revised schedules by reworking all or a large part of the schedule without regard for the extent of the changes between the old and new schedules. In other words, these methods do not attempt to minimize scheduling perturbations when a schedule must be revised. Such extensive scheduling changes can be disruptive to the smooth operation of a complex activity. Further, reworking the entire schedule causes these methods to take an undesirably long time to produce a schedule. Thus, none of the above-described methods work well for frequent rescheduling of a complex activity. Since, in the real world, rescheduling must typically be done often to respond to changing conditions, a better scheduling approach is needed, one that integrates the resolution of capacity and inventory constraints, that minimizes the disturbances caused by rescheduling and that produces a revised schedule quickly. Further, such a system should be easily modified to accommodate changes in constraint definition.